perm filename INTRO[0,BGB]8 blob
sn#109015 filedate 1974-07-02 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 ~M2BDJ25.FNT[XGP,SYS]
C00005 00003 ~λ40JAFATITLE PAGE - 2.~JRFA AUGUST 1974.
C00007 00004 ~λ40JCFD CONTENTS.
C00008 00005 ~JVλ5JCFD DETAILED TABLE OF CONTENTS.
C00010 00006 ~JCFD LIST OF BOXES.
C00011 00007 ~JCFD LIST OF FIGURES.
C00013 00008 ~JCFD ACKNOWLEDGEMENTS.
C00014 00009 ~αINTRODUCTIONP1λ30JCFA SECTION 0.
C00018 00010 Once acquired, a 3-D model can be used to anticipate the
C00021 ENDMK
C⊗;
~M2BDJ25.FNT[XGP,SYS];
FA~FD~F1
TITLE PAGE - 1. AUGUST 1974.
draft - draft - draft - draft - draft - draft - draft - draft - draft
~I400,0;JC;FD GEOMETRIC MODELING FOR COMPUTER VISION.
~I600,0;JC;FD BRUCE G. BAUMGART
~I800,0;λ17;JU;FAABSTRACT:
The main idea of this thesis is that a 3-D geometric model of
the physical world is an essential part of a general purpose vision
system. Such a model provides a goal for descriptive image analysis,
an origin for image synthesis (for verification), and a context for
spatial problem solving. Some of the design ideas to be presented
have been implemented in two programs named GEOMED and CRE; the
programs are demonstrated in situations involving camera motion
relative to a static world.
~λ5;H2;I1600,0;V1600,1260;I1600,0;JU;F2
This research was supported in part by the Advanced Research
Projects Agency of the Office of the Secretary of Defense under
Contract No. SD-183.
The views and conclusions contained in this document are
those of the author and should not be interpreted as necessarily
representing the official policies, either expressed or implied, of
the Advanced Research Project Agency
or the United States Government.
~λ40;JA;FATITLE PAGE - 2.~JR;FA AUGUST 1974.
~I400,0;JC;FD GEOMETRIC MODELING FOR COMPUTER VISION.
~JCFA A DISSERTATION
~JCFA SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE
~JCFA AND THE COMMITTEE ON GRADUATE STUDIES
~JCFA OF STANFORD UNIVERSITY
~JCFA IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
~JCFA FOR THE DEGREE OF
~JCFA DOCTOR OF PHILOSOPHY
~JCFA BY
~JCFA BRUCE G. BAUMGART
~JCFA AUGUST 1974
~H4;
I310,0;V310,1260;
I460,0;V460,1260;
I1020,0;V1020,1260;
I1260,0;V1260,1260;
I1900,0;JC;FA- i -
~λ40;JCFD CONTENTS.
~JAFA
{INTRO} 0. INTRODUCTION.
{GEM} 1. GEOMETRIC MODELING THEORY.
{WINGED} 2. THE WINGED EDGE POLYHEDRON REPRESENTATION.
{GEOMED} 3. A GEOMETRIC MODELING COMMAND LANGUAGE.
{OCCULT} 4. HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
{BIN} 5. A POLYHEDRON INTERSECTION ALGORITHM.
{CNTOUR} 6. VIDEO IMAGE CONTOURING.
{CMPARE} 7. IMAGE COMPARING.
{CAMERA} 8. CAMERA AND FEATURE LOCUS SOLVING.
{VIS} 9. COMPUTER VISION THEORY.
{CONCLU} 10. CONCLUSION.
APPENDICES:
{REF} REFERENCES.
{GNODES} GEOMED NODE FORMATS.
{CNODES} CRE NODE FORMATS.
~I1900,0;JC;FA- ii -
~JV;λ5;JCFD DETAILED TABLE OF CONTENTS.
~FA
SECTION 0. INTRODUCTION.
SECTION 1. GEOMETRIC MODELING THEORY.
1.0 Introduction to Geometric Modeling.
1.1 Kinds of Geometric Models.
1.2 Polyhedron Definitions.
1.3 Camera, Light and Image Modeling.
SECTION 2. THE WINGED EDGE POLYHEDRON REPRESENTATION.
2.0 Introduction to the Winged Edge.
2.1 Winged Edge Link Fields.
2.2 Perimeter Accessing.
2.3 Edge and Face Splitting.
2.4 Basic Polyhedron Synthesis.
2.5 Coordinate Free Polyhedron Representation.
SECTION 3. A GEOMETRIC MODELING COMMAND LANGUAGE.
3.0 Introduction to GEOMED.
3.1 Euler Routines.
3.2 Euclidean Routines.
3.3 Image Synthesis Routines.
SECTION 4. HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
SECTION 5. A POLYHEDRON INTERSECTION ALGORITHM.
SECTION 6. VIDEO IMAGE CONTOURING.
SECTION 7. IMAGE COMPARING.
SECTION 8. CAMERA AND FEATURE LOCUS SOLVING.
SECTION 9. COMPUTER VISION THEORY.
SECTION 10. CONCLUSION.
~I1900,0;JC;FA- iii -
~JCFD LIST OF BOXES.
~JAFA
SECTION 0. INTRODUCTION.
SECTION 1. GEOMETRIC MODELING THEORY.
SECTION 2. THE WINGED EDGE POLYHEDRON REPRESENTATION.
SECTION 3. A GEOMETRIC MODELING COMMAND LANGUAGE.
SECTION 4. HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
SECTION 5. A POLYHEDRON INTERSECTION ALGORITHM.
SECTION 6. VIDEO IMAGE CONTOURING.
SECTION 7. IMAGE COMPARING.
SECTION 8. CAMERA AND FEATURE LOCUS SOLVING.
SECTION 9. COMPUTER VISION THEORY.
SECTION 10. CONCLUSION.
~I1900,0;JC;FA- iv -
~JCFD LIST OF FIGURES.
~JAFA
SECTION 0. INTRODUCTION.
0.1 Example of Descriptive Vision.
Two objects derived from turntable pictures.
0.2 Example of Verification Vision - water pump parts.
SECTION 1. GEOMETRIC MODELING THEORY.
SECTION 2. THE WINGED EDGE POLYHEDRON REPRESENTATION.
SECTION 3. A GEOMETRIC MODELING COMMAND LANGUAGE.
SECTION 4. HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
SECTION 5. A POLYHEDRON INTERSECTION ALGORITHM.
SECTION 6. VIDEO IMAGE CONTOURING.
SECTION 7. IMAGE COMPARING.
SECTION 8. CAMERA AND FEATURE LOCUS SOLVING.
SECTION 9. COMPUTER VISION THEORY.
SECTION 10. CONCLUSION.
~I1900,0;JC;FA- v -
~JCFD ACKNOWLEDGEMENTS.
~FA
The following people personally contributed to this work:
Thesis Adviser: John Mc Carthy
Readers: Jerome A. Feldman
Donald E. Knuth
Alan C. Kay
Jerry Agin, Leona Baumgart, Tom Binford, Jack Buchanan, Les Earnest,
Tom Gafford, Steve Gibson, Ralph Gorin, Tovar Mock, Andy Moorer,
Hans Moravec, Richard Orban, Ted Panofsky, Lou Paul, Lynn Quam,
Jeff Raskin, Ron Rivest, Irwin Sobel, Robert Sproull, Ivan Sutherland,
Dan Swinehart, Russel Taylor, Marty Tenenbaum, Arthur Thomas.
~I1900,0;JC;FA- vi -
~αINTRODUCTION;P1;λ30;JCFA SECTION 0.
~JCFD INTRODUCTION.
~JU;λ7;FM
"For the purpose of presenting my argument I must first
explain the basic premise of sorcery as don Juan presented it to me.
He said that for a sorcerer, the world of everyday life is not real,
or out there, as we believe it is. For a sorcerer, reality or the
world we all know, is only a description. For the sake of validating
this premise don Juan concentrated the best of his efforts into
leading me to a genuine conviction that what I held in mind as the
world at hand was merely a description of the world; a description
that had been pounded into me from the moment I was born."
~JR;FM - Carlos Castaneda. Journey to Ixtlan.
~JU;λ30;FA
This thesis is about computer techniques for handling 3-D
geometric descriptions of the world; the world that can be visually
perceived with a television camera. The overall design idea may be
characterized as an inverse computer graphics approach to computer
vision. In computer graphics, the world is represented in sufficient
detail so that the image forming process can be numerically simulated
to generate synthetic television images; in the inverse, perceived
television pictures (from a real TV camera) are analysed to compute
detailed geometric models. For example, the polyhedra in figure 1.1
were automatically computed by viewing various objects on a
turntable. It is hoped, that visually acquired 3-D geometric models
can be of use to other robotic processes such as manipulation,
navigation or recognition.
~λ9;F.{figure 0.1 two panels this page; panel A: blocks, panel B: horse}
{figure 0.2
panel A: Corrected Word Model. Panel B: Initial World Model.
panel C: Perceived Contour Image. Panel D: Predicted Contour Image.
panel E: Perceived Video Image. Panel F: Predicted Video.}
~λ30;Q;F.
Once acquired, a 3-D model can be used to anticipate the
appearance of an object in a scene, making feasible a quantitative
form of vision by verification (feedback vision). For example, the
predicted video appearance of the two machine parts depicted in
figure 0.2B can be computed (figure 0.2F to 0.2D) and compared with
anaylsis of an actual video image of the parts (figure 0.2E to 0.2C).
By comparing the predicted image with a perceived image, the
correspondence between features of the internal model and features of
the external reality can be established and a corrected location of the
parts and the camera can be measured (figure 0.2A).
Finally by way of introduction, I wish to emphasive that the
kind of vision being attempted is metric rather than semantic and
that the results achieved to date are modest. Feature classification
and recognition in terms of English words is not being attempted,
rather a system of prediction and correction beteen a 3-D world model
and a sequence of images is contemplated. The chapters of this thesis
proceed from theory, through implementation, and back to theory;
with the first five chapters dealing with modeling and the last five
chapters dealing with vision. The theory consists of two parts: the
first, on geometric modeling in chapter one and the second on vision
in chapter nine. The implementation consists of two main programs named
GEOMED and CRE. CRE is a solution to the problem of finding intensity
contours in a sequence of television pictures and of linking
corresponding contours between pictures. GEOMED is a system of 3-D
modeling routines with which arbitrary polyhedra may be constructed,
altered, or viewed in perspective with hidden lines eliminated.